#include <iostream>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
#include <ctime>

using namespace std;
template <class k>
struct HashFunc
{
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};
//特化//
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 131;
			hash += e;
		}
		return hash;
	}
};
//struct HashFuncString
//{
//	size_t operator()(const string& key)
//	{
//		size_t hash = 0;
//		for (auto e : key)
//		{
//			hash *= 131;
//			hash += e;
//		}
//		return hash;
//	}
//};

namespace closehash
{
	enum State//用来标志该位置的状况：empty空，exist有数据，delete删除
	{
		EMPTY,
		EXIST,
		DELETE,
	};
	template <class k, class v>
	struct HashData
	{
		pair<k, v> _kv;//自定义类型，会初始化
		State _state = EMPTY;//初始化
	};

	template <class k, class v, class Hash = HashFunc<k>>
	class HashTable
	{
		typedef HashData<k, v> Data;
	public:
		HashTable()
			:_n(0)
		{
			_tables.resize(10);//解决除0错误
		}
		bool Insert(const pair<k, v>& kv)
		{
			if (Find(kv.first))
				return false;
			//if (_n  % _tables.size() >= 0.7)//负载因子大于7就要扩容，不然线性探测几乎走了整个结构
			if (_n * 10 / _tables.size() >= 7)//内置类型不做处理，所以_n要初始化为0，这里就发生了除0错误
			{
				//旧表数据重新计算映射到新表
				//vector<Data> newTable;
				//newTable.resize(_tables.size() * 2);
				//for ()
				//{
				//	// ...这里重新推导下面的hashi和while循环等代码
				//}
				HashTable<k, v, Hash> newHL;
				newHL._tables.resize(_tables.size() * 2);
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
					{
						newHL.Insert(e._kv);//优势就是复用insert。上面不能复用
					}
				}
				_tables.swap(newHL._tables);
			}
			Hash hf;
			size_t hashi = hf(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _tables.size();//为了防止hashi加到越界了，每次都要余等表的大小
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;
			return true;
		}
		Data* Find(const k& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			size_t starti = hashi;//用来记录hashi最开始的地址，如果hashi走了一圈又回到了这里，那么就找不到key
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
				//如果表的标志为有数据，且值相等，返回
				{
					return &_tables[hashi];
				}
				++hashi;
				hashi %= _tables.size();
				if (hashi == starti)//如果哈希表都是删除标记和存在标记，那么哈希表就永远不为空
				{
					break;
				}
			}
			return nullptr;
		}
		bool Erase(const k& key)
		{
			Data* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}
	private:
		vector<Data> _tables;
		size_t _n = 0;//哈希表有效数据个数
	};

	void TestHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 18, 8, 7, 27, 57, 3, 38, 18 };
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}

		ht.Insert(make_pair(17, 17));
		ht.Insert(make_pair(5, 5));
		cout << ht.Find(7) << endl;
		cout << ht.Find(8) << endl;

		ht.Erase(7);
		cout << ht.Find(7) << endl;
		cout << ht.Find(8) << endl;
	}

	void TestHT2()//整型可以直接取余，字符串不行
	{
		string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜",
					"苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		//HashTable<string, int, HashFuncString> cnthl;
		HashTable<string, int> cnthl;//特化
		for (auto& e : arr)
		{
			HashData<string, int>* ret = cnthl.Find(e);
			if (ret)
			{
				ret->_kv.second++;
			}
			else
			{
				cnthl.Insert(make_pair(e, 1));
			}
		}

		HashFunc<string> hf;
		cout << hf("abc") << endl;
		cout << hf("bac") << endl;
		cout << hf("cba") << endl;
		cout << hf("aad") << endl;
	}
}

int main()
{
    closehash::TestHT1();
    closehash::TestHT2();
    return 0;
}
